#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/29 11:56
# @USER    : Shengji He
# @File    : ShortestPalindrome.py
# @Software: PyCharm
# @Version  : Python-
# @TASK: KMP algorithm


class Solution:
    def shortestPalindrome(self, s: str) -> str:
        """
        Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it.
        Find and return the shortest palindrome you can find by performing this transformation.

        Example 1:
            Input: "aacecaaa"
            Output: "aaacecaaa"
        Example 2:
            Input: "abcd"
            Output: "dcbabcd"

        :param s:
        :return:
        """
        n = len(s)
        # KMP algorithm, generate LPS (longest prefix suffix) array
        fail = [-1] * n
        for i in range(1, n):
            j = fail[i - 1]
            while j != -1 and s[j + 1] != s[i]:
                j = fail[j]
            if s[j + 1] == s[i]:
                fail[i] = j + 1
        # reverse and find longest sub str matching!
        best = -1
        for i in range(n - 1, -1, -1):
            while best != -1 and s[best + 1] != s[i]:
                best = fail[best]
            if s[best + 1] == s[i]:
                best += 1
        add = ('' if best == n - 1 else s[best + 1:])
        return add[::-1] + s

    def shortestPalindromeCustom(self, s: str) -> str:
        """
        Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it.
        Find and return the shortest palindrome you can find by performing this transformation.

        Example 1:
            Input: "aacecaaa"
            Output: "aaacecaaa"
        Example 2:
            Input: "abcd"
            Output: "dcbabcd"

        :param s:
        :return:
        """
        """
        思路：目标是最短的回文串，通过在头部补充元素；需要找出输入字符串s中最长的回文串，然后将多余部分逆序插入头部
        如何找s中最长回文串，相当于把字符串s逆序为s'，然后将s与s'进行字符串匹配，找出匹配最长的长度，即回文串，剩余部分则是待补充的
        字符串匹配则是利用KMP进行高效匹配
        """
        n = len(s)
        s_state = [0] * n
        for i in range(1, n):
            j = s_state[i - 1]
            while j != 0 and s[j] != s[i]:
                j = s_state[j - 1]
            if s[j] == s[i]:
                s_state[i] = j + 1
        best_j = 0
        for i in range(n-1, -1, -1):
            while best_j != 0 and s[best_j] != s[i]:
                best_j = s_state[best_j - 1]

            if s[best_j] == s[i]:
                best_j += 1
        extra_str = '' if best_j == n else s[best_j:]
        out = extra_str[::-1] + s
        return out




if __name__ == '__main__':
    S = Solution()
    # s = 'aacecaaa'
    s = 'caacecaaa'
    print(S.shortestPalindrome(s))
    print(S.shortestPalindromeCustom(s))
    print('done')
